package com.my.algorithmlearning.leetcode;

import com.my.algorithmlearning.entity.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName Medium_105_BuildTreeFromPreAndInOrder
 * @Description Medium_105_BuildTreeFromPreAndInOrder
 * @Author wanghaiwei
 * @Date 2023/3/30 13:54
 */
public class Medium_105_BuildTreeFromPreAndInOrder {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null) {
            return null;
        }
        if (preorder.length == 1 && inorder.length == 1) {
            return new TreeNode(preorder[0]);
        }
        Map<Integer, Integer> inOrderIdxMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inOrderIdxMap.put(inorder[i], i);
        }
        return doBuild(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1, inOrderIdxMap);
    }

    private TreeNode doBuild(int[] preorder, int[] inorder, int preOrderStartIdx, int preOrderEntIdx, int inOrderStartIdx, int inOrderEndIdx
            , Map<Integer, Integer> inOrderIdxMap) {
        if (preOrderStartIdx == preOrderEntIdx || inOrderStartIdx == inOrderEndIdx) {
            return new TreeNode(preorder[preOrderStartIdx]);
        }
        TreeNode root = new TreeNode(preorder[preOrderStartIdx]);
        //找到中序的根节点位置，拆分为左右子节点
        int rootIdxOfInOrder = inOrderIdxMap.get(preorder[preOrderStartIdx]);
        //左子树的节点个数
        int numOfLeftNodes = rootIdxOfInOrder - inOrderStartIdx;
        //左子树在先序中的开始节点
        int leftTreePreOrderStartIdx = preOrderStartIdx + 1;
        //左子树在先序中的结束节点
        int leftTreePreOrderEndIdx = leftTreePreOrderStartIdx + numOfLeftNodes - 1;
        //左子树在中序的开始节点
        int leftTreeInOrderStartIdx = inOrderStartIdx;
        //左子树中序的结束节点
        int leftTreeInOrderEndIdx = rootIdxOfInOrder - 1;
        if (numOfLeftNodes > 0) {
            root.left = doBuild(preorder, inorder, leftTreePreOrderStartIdx, leftTreePreOrderEndIdx, leftTreeInOrderStartIdx, leftTreeInOrderEndIdx, inOrderIdxMap);
        }
        //右子树的节点个数
        int numOfRightNodes = inOrderEndIdx - rootIdxOfInOrder;
        //右子树在先序中的开始节点
        int rightTreePreOrderStartIdx = leftTreePreOrderEndIdx + 1;
        //右子树在先序中的结束节点
        int rightTreePreOrderEndIdx = rightTreePreOrderStartIdx + numOfRightNodes - 1;
        //右子树在中序的开始节点
        int rightTreeInOrderStartIdx = rootIdxOfInOrder + 1;
        //右子树中序的结束节点
        int rightTreeInOrderEndIdx = inOrderEndIdx;
        if (numOfRightNodes > 0) {
            root.right = doBuild(preorder, inorder, rightTreePreOrderStartIdx, rightTreePreOrderEndIdx, rightTreeInOrderStartIdx, rightTreeInOrderEndIdx, inOrderIdxMap);
        }
        return root;
    }

    public static void main(String[] args) {
        Medium_105_BuildTreeFromPreAndInOrder solution = new Medium_105_BuildTreeFromPreAndInOrder();
        TreeNode result = solution.buildTree(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7});
        System.out.println("Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]的输出：" + result.toString());

        result = solution.buildTree(new int[]{-1}, new int[]{-1});
        System.out.println("Input: preorder = [-1], inorder = [-1]的输出：" + result.toString());
    }
}
